第 118 场力扣夜喵双周赛

查找包含给定字符的单词

模拟。

class Solution {
    public List<Integer> findWordsContaining(String[] words, char x) {
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            if (words[i].contains(x + "")) {
                ans.add(i);
            }
        }
        return ans;
    }
}

最大化网格图中正方形空洞的面积

分别求出行和列的最长连续线段，然后最大正方形面积就是两者最小值加一的平方。

class Solution {
    public int maximizeSquareHoleArea(int n, int m, int[] hBars, int[] vBars) {
        Arrays.sort(hBars);
        Arrays.sort(vBars);
        int maxH = 0, maxV = 0;
        for (int i = 0, j = 0; j < hBars.length; j++) {
            if (hBars[j] - hBars[i] == j - i) {
                maxH = Math.max(maxH, j - i + 1);
            } else {
                i = j;
            }
        }
        for (int i = 0, j = 0; j < vBars.length; j++) {
            if (vBars[j] - vBars[i] == j - i) {
                maxV = Math.max(maxV, j - i + 1);
            } else {
                i = j;
            }
        }
        int len = Math.min(maxH, maxV) + 1;
        return len * len;
    }
}

购买水果需要的最少金币数

动态规划，\(dp[i]\) 表示获取 \([i,n]\) 范围内所有水果所需的最少金币数，有 \(dp[i]=prices[i]+\min_{j=i+1}^{2i+1}{dp[j]}\)，时间复杂度 \(O(n^{2})\)。

class Solution {
    public int minimumCoins(int[] prices) {
        int n = prices.length;
        for (int i = (n + 1) / 2 - 1; i > 0; i--) {
            int min = Integer.MAX_VALUE;
            for (int j = i + 1; j <= 2 * i + 1; j++) {
                min = Math.min(min, prices[j - 1]);
            }
            prices[i - 1] += min;
        }
        return prices[0];
    }
}

单调队列优化，时间复杂度 \(O(n)\)。

class Solution {
    public int minimumCoins(int[] prices) {
        int n = prices.length;
        Deque<Integer> q = new ArrayDeque<>();
        for (int i = n; i > 0; i--) {
            while (!q.isEmpty() && q.peekFirst() > 2 * i + 1) {
                q.pollFirst();
            }
            if (i <= (n + 1) / 2 - 1) {
                prices[i - 1] += prices[q.peekFirst() - 1];
            }
            while (!q.isEmpty() && prices[q.peekLast() - 1] >= prices[i - 1]) {
                q.pollLast();
            }
            q.offerLast(i);
        }
        return prices[q.peekLast() - 1];
    }
}

找到最大非递减数组的长度

单调队列优化 DP，随缘补题。